package Aula20;

public class AVLImpl implements AVL {

        private ArvoreBinaria bst;
        private final String SIMPLES_D = "ROT_S_DIR";
        private final String SIMPLES_E = "ROT_S_ESQ";
        private final String DUPLO_ED = "ROT_D_ESQ_DIR";
        private final String DUPLO_DE = "ROT_D_DIR_ESQ";
        private int keyAdicionado;

        public AVLImpl() {
                bst = new ArvoreBinaria();
        }

        private int fatorB(AVLNode no) {
                int leftHeight = 0;
                int rightHeight = 0;
                if (no.left != null) {
                        leftHeight = no.left.height;
                }
                if (no.right != null) {
                        rightHeight = no.right.height;
                }
                return rightHeight - leftHeight;
        }

        private boolean isBalanced(AVLNode no) {
                int bf = fatorB(no);
                return (-1 <= bf) && (bf <= 1);
        }

        private AVLNode tallerChild(AVLNode pai) {
                int leftHeight = 0;
                int rightHeight = 0;
                if (pai.left != null) {
                        leftHeight = pai.left.height;
                }
                if (pai.right != null) {
                        rightHeight = pai.right.height;
                }
                if (leftHeight < rightHeight)
                        return pai.right;
                return pai.left;
        }

        private void rotSimplesDir(AVLNode no, AVLNode filho, AVLNode neto) {
                AVLNode t2 = filho.right;
                AVLNode pai = no.parent;

                filho.parent = pai;
                if (pai != null) {
                        if (pai.left == no) {
                                pai.left = filho;
                        } else {
                                pai.right = filho;
                        }
                }

                filho.right = no;
                no.parent = filho;
                no.left = t2;
                if(t2 != null)
                        t2.parent = no;

        }

        private void rotSimplesEsq(AVLNode no, AVLNode filho, AVLNode neto) {
                AVLNode t1 = filho.left;
                AVLNode pai = no.parent;

                filho.parent = pai;
                if (pai != null) {
                        if (pai.left == no) {
                                pai.left = filho;
                        } else {
                                pai.right = filho;
                        }
                }

                filho.left = no;
                no.parent = filho;
                no.right = t1;
                if(t1 != null)
                        t1.parent = no;

        }

        private void rotDuplaEsqDir(AVLNode no, AVLNode filho, AVLNode neto) {
                AVLNode t1 = neto.right;
                AVLNode t2 = neto.left;
                AVLNode pai = no.parent;

                neto.parent = pai;
                if (pai != null) {
                        if (pai.left == no) {
                                pai.left = neto;
                        } else {
                                pai.right = neto;
                        }
                }

                neto.left = filho;
                neto.right = no;
                no.parent = neto;
                no.left = t1;
                if(t1 != null)
                        t1.parent = no;
                filho.parent = neto;
                filho.right = t2;
                if(t2 != null)
                        t2.parent = filho;
        }

        private void rotDuplaDirEsq(AVLNode no, AVLNode filho, AVLNode neto) {
                AVLNode t1 = neto.left;
                AVLNode t2 = neto.right;
                AVLNode pai = no.parent;

                neto.parent = pai;
                if (pai != null) {
                        if (pai.left == no) {
                                pai.left = neto;
                        } else {
                                pai.right = neto;
                        }
                }

                neto.left = no;
                neto.right = filho;
                no.parent = neto;
                no.right = t1;
                if(t1 != null)
                        t1.parent = no;
                filho.parent = neto;
                filho.left = t2;
                if(t2 != null)
                t2.parent = filho;
        }

        private RetRestructure restructure(AVLNode no) {
                AVLNode filho = tallerChild(no);
                AVLNode neto = tallerChild(filho);
                if (no.left == filho) {
                        if (filho.left == neto) {
                                // Simples DIR
                                rotSimplesDir(no, filho, neto);
                               
                                if(filho.parent == null){
                                        bst.raiz = filho;
                                }
                               
                                String rotacao = SIMPLES_D + "(" + keyAdicionado + ", " + no.key + ")";
                                return new RetRestructure(filho, rotacao);
                        } else {
                                // DUPLA ESQ-DIR
                                rotDuplaEsqDir(no, filho, neto);
                               
                                if(neto.parent == null){
                                        bst.raiz = neto;
                                }
                               
                                String rotacao = DUPLO_ED + "(" + keyAdicionado + ", " + filho.key + "/" + no.key + ")";
                                return new RetRestructure(neto, rotacao);
                        }
                } else {
                        if (filho.right == neto) {
                                // Simples ESQ
                                rotSimplesEsq(no, filho, neto);
                               
                                if(filho.parent == null){
                                        bst.raiz = filho;
                                }
                               
                                String rotacao = SIMPLES_E + "(" + keyAdicionado + ", " + no.key + ")";
                                return new RetRestructure(filho, rotacao);
                        } else {
                                // DUPLA DIR-ESQ
                                rotDuplaDirEsq(no, filho, neto);
                               
                                if(neto.parent == null){
                                        bst.raiz = neto;
                                }
                               
                                String rotacao = DUPLO_DE + "(" + keyAdicionado + ", " + filho.key + "/" + no.key + ")";
                                return new RetRestructure(neto, rotacao);
                        }
                }
        }

        private String rebalance(AVLNode no) {
                String saida = "";
                while (bst.raiz != no) {
                        no = no.parent;
                        setHeight(no);
                        if (!isBalanced(no)) {
                                RetRestructure ret = this.restructure(no);
                                if(!saida.equals("")){
                                        saida += ", ";
                                }
                                saida += ret.rotacao;
                                no = ret.no;
                                setHeight(no.left);
                                setHeight(no.right);
                                setHeight(no);
                        }
                }
                setHeight(no);
                return saida;
        }


        private void setHeight(AVLNode no) {
                int leftHeight = 0;
                int rightHeight = 0;
                if (no.left != null) {
                        leftHeight = no.left.height;
                }
                if (no.right != null) {
                        rightHeight = no.right.height;
                }
                no.height = (Math.max(leftHeight, rightHeight)) + 1;            
        }
       
        private String inserir(int key){
                String saida = "";
                if(key > 0){
                        AVLNode no = bst.insert(key);
                        if(no != null){
                                keyAdicionado = key;
                                saida = rebalance(no);
                        }
                }
                return saida;
        }

        public String buscar(int numero) {
                AVLNode no = bst.search(numero);
                if (no != null) {
                        //Como no exemplo nao considera o NIL e aqui consideramos, entao eu reduzo a altura em 1, pra desconsiderar o NIL.
                        return fatorB(no) + ", " + (no.height - 1);
                }
                return null;
        }

        public String montarArvore(int[] numerosDaArvore) {
                String saida = "";
                String ret;
                for(int num : numerosDaArvore){
                        ret = inserir(num);
                        if(!saida.equals("") && !ret.equals("")){
                                saida += ", ";
                        }
                        saida += ret;
                }
                return saida;
        }

        public String remover(int numero) {
        	String saida = "";
        	AVLNode n = bst.remove(numero);
       		 if(n != null){
       			 keyAdicionado = n.parent.key;
                 saida = rebalance(n);
             }
        	return saida;
        }
       
        public static void main(String[] args) {
                 AVL avl = new AVLImpl();
               
                int [] numeros = {41, 38, 31, 12, 19, 8, 27, 49, 45};
                System.out.println(avl.montarArvore(numeros));

                System.out.println(avl.buscar(31));
                System.out.println(avl.buscar(38));
                System.out.println(avl.buscar(25));
                System.out.println(avl.buscar(19));

              System.out.println(avl.remover(8));
              System.out.println(avl.remover(41));
              System.out.println(avl.remover(60));    
              System.out.println(avl.remover(12));
        }
}

